class ListNode {
    int val;
    //套定义ListNode类型
    ListNode next;
    ListNode(int x) { val = x; }
}

class PalindromeLinkedList {
    public static void main(String[] args) {
        // 创建第有序链表 1 -> 2 -> 4 -> 1 -> 3 -> 4
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(2);
        list1.next.next = new ListNode(4);
        list1.next.next.next = new ListNode(1);
        list1.next.next.next.next = new ListNode(3);
        list1.next.next.next.next.next = new ListNode(4);

        boolean palindrome = Solution.chkPalindrome(list1);

        System.out.println("回文？" + palindrome);
    }

    static class Solution {
        public static boolean chkPalindrome(ListNode A) {
            ListNode slow = A;
            ListNode fast = A;

            if (A == null || A.next == null) {
                return true;
            }

            while (fast != null && fast.next != null) { //快慢指针法
                fast = fast.next.next;
                slow = slow.next;
            }

            ListNode i = slow.next;
            //举例为1 -> 2 -> 3 -> 4 -> 5
            while (i != null) {         //翻转
                ListNode Next = i.next;
                i.next = slow;          //.next在左，链表被重构
                //上行使链表指向slow
                slow = i;
                //1 <- 2   3 -> 4 -> 5
                i = Next;
            }

//翻转链表的行为使链表表现为：1 -> 2 -> 3    4 <- 5 <- 6    (3、4之间被5隔开)
//而中间的“   ”使得左右指针无法相遇，从而立即切断，下一个节点为空
//添节点和删节点也会改变链表

/*  ***添***
    point2.next = point1.next;      2的下一个为1的下一个（对应主链表）
    point1.next = point2;           1的下一个为2
*/
//  head.next = head.next.next;     ***删***

            while (slow != null) {
                if (A.val != slow.val) {
                    return false;
                }

                if (A.next == slow) {
                    return true;
                }

                A = A.next;
                slow = slow.next;
            }

            return true;
        }
    }
}